package org.example.l0;

import org.junit.jupiter.api.Test;

public class longestValidParentheses {

    @Test
    void aa() {
        String a = "())((())";
        int i = longestValidParentheses(a);
        System.out.println(i);
    }

    public int longestValidParentheses(String s) {
        int maxans = 0, len = s.length();
        int[] dp = new int[len];

        for (int i = 1; i < len; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = pre(i - 2, dp) + 2;
                } else {
                    int matchIdx = i - dp[i - 1] - 1;
                    if (matchIdx >= 0 && s.charAt(matchIdx) == '(') {
                        dp[i] = dp[i - 1] + pre(matchIdx - 1, dp) + 2;
                    }
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }

        return maxans;
    }

    private int pre(int idx,
                    int[] dp) {
        if (idx < 0) {
            return 0;
        }

        return dp[idx];
    }

}
